\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb,graphicx,url,charter}

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.2in { {\bf CS390 Computational Game Theory and Mechanism Design}
     	 \hfill #2 }
       \vspace{4mm}
       \hbox to 6.2in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.2in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\handout}[3]{\heading{#1}{#2}{Feng Shi}{}{#3}}

\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}

\handout{1}{2013.7.10}{Problem Set 3}

\paragraph{Problem 1} (No collaborater.)

(NRTV07, Exercise 17.1.) Suppose that we modify Pigou's example so that the lower edge has cost 
function $c_2(x) = (x/n)^d$ for some $d\geq 1$. What is the price of anarchy of the resulting 
selfish routing network when $n$ goes to infinity, as a function of $d$?
What does the price of anarchy become when $d$ goes to infinity?
(That is, first compute the PoA for any fixed $d$ with $n\rightarrow +\infty$,
and then compute the limit of this function as $d\rightarrow +\infty$.)

\textbf{Solution:}

The cost function for routing $x$ units of traffic on the lower edge is 
$$c(x)=x(\frac{x}{n})^d+(n-x), \ x\in[0,1]$$
Since $(x/n)^d\leq 1$, there are $2$ equilibria: $x=n$ and $x=n-1$.
So the price of anarchy is 
$$\displaystyle PoA=\frac{c(n)}{\min_{\substack{x\in[0,n]}}c(x)}\mbox{ or }
 PoA=\frac{c(n-1)}{\min_{\substack{x\in[0,n]}}c(x)}$$
Take the deriviation of $c(x)$ and solve for $c'(x)=0$ gives $\displaystyle x=\frac{n}{(d+1)^{1/d}}$
and $c''(x)\geq 0$ for $x\in[0,n]$, so at $\displaystyle x=\frac{n}{(d+1^{1/d})}$, $c(x)$ is optimal.
So
$$PoA=\frac{c(n)}{\min_{\substack{x\in[0,n]}}c(x)}
=\frac{(1+d)^{(1+1/d)}}{(1+d)^{(1+1/d)}-d}\mbox{ or }
PoA=\frac{c(n-1)}{\min_{\substack{x\in[0,n]}}c(x)}
=\frac{(\frac{n-1}{n})^{(d+1)}+1}{1-\frac{d}{(d+1)^{(1+1/d)}}}$$
When $n\to\infty$, $\displaystyle PoA\to\frac{(1+d)^{(1+1/d)}}{(1+d)^{(1+1/d)}-d}$.\\
When $d\to\infty$, $\displaystyle PoA\to\frac{e}{e-1}$.

\bigskip

\paragraph{Problem 2} (No collaborater.)

(NRTV07, Exercise 19.9.) Prove that in any Shapley network design game, 
the price of anarchy can never exceed $n$, the number of players.

\textbf{Solution:}

Suppose $S$ is a Nash equilibrium, let $OPT$ denote the cost of a social optimun. 
Let $\pi_i$ be the shortest path in graph $G$ from $s_i$ to $t_i$.
Then $$cost_i(S)\leq cost_i(S_{-i},\pi_i)\leq d_G(s_i,t_i)\leq \ (OPT)$$
$\quad $and $$cost(S)=\sum_i cost_i(S)\leq n \ (OPT)$$
\bigskip

\paragraph{Problem 3} (No collaborator.)

(NRTV07, Exercise 17.3.) Consider minimizing the following objective function in the scheduling game
with $n$ players and $n$ machines: for any pure strategy profile $s$, $f(s) = \sum_i c_i(s)$,
and for any mixed strategy profile $\sigma$, $f(\sigma) = \mathbb{E}_{s\thicksim \sigma} f(s)$.
Compute the price of anarchy, taking into consideration all mixed NEs.


\bibliographystyle{agsm}

\begin{thebibliography}{99}

\bibitem{OR94}{M. J. Osborne and A. Rubinstein. {\em A course in game theory.} MIT Press, 1994.}

\bibitem{NRTV07}{N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds).
	\\{\em Algorithmic game theory.} Cambridge University Press, 2007. }

\textbf{Solution:}
\end{thebibliography}

\end{document}
